﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TreeDemo
{
    class BinarySearchTree
    {
        public BinarySearchTree(int[] input)            
        {            
            ReadInput(input);
        }

        public BinarySearchTreeNode xNode, yNode, zNode;
        public BinarySearchTreeNode rootNode;
        

        public void Add(int data)
        {
            xNode = yNode = zNode = null;
            AddNode(rootNode, data);
        }

        public void Remove(int data)
        {
            RemoveNode(rootNode, data);
        }

        private BinarySearchTreeNode RemoveNode(BinarySearchTreeNode node, int data)
        {
            if (node == null)
                return null;

            if (node.data == data)
            {
                if (node.left == null && node.right == null)
                    return null;

                if (node.left != null)
                {
                    BinarySearchTreeNode temp = node;
                    node = node.left;
                    BinarySearchTreeNode temp1 = node;
                    BinarySearchTreeNode temp2 = temp1;

                    if (temp1 != null)
                    {
                        while (temp1.right != null)
                        {
                            temp2 = temp1;
                            temp1 = temp1.right;
                        }
                    }

                    if (rootNode == temp)
                        rootNode = temp1;
                    temp2.right = temp1.left;
                    temp1.left = temp.left != temp1 ? temp.left : temp1.left;
                    temp1.right = temp.right;
                    node = temp1;
                }
                else if (node.right != null)
                {
                    BinarySearchTreeNode temp = node;
                    node = node.right;
                    BinarySearchTreeNode temp1 = node;
                    BinarySearchTreeNode temp2 = temp1;

                    if (temp1 != null)
                    {
                        while (temp1.left != null)
                        {
                            temp2 = temp1;
                            temp1 = temp1.left;
                        }
                    }

                    if (rootNode == temp)
                        rootNode = temp1;
                    temp2.left = temp1.right;
                    temp1.right = temp.right != temp1 ? temp.right : temp1.right;
                    temp1.left = temp.left;
                }
            }
            else if (data > node.data)
            {
                node.right = RemoveNode(node.right, data);
                node = Shift(node);
            }
            else if (data < node.data)
            {
                node.left = RemoveNode(node.left, data);
                node = Shift(node);
            }
            return node;
        }

        private BinarySearchTreeNode AddNode(BinarySearchTreeNode node, int data)
        {

            if (node == null)
            {
                node = new AVLTreeNode(data);
                if (rootNode == null) rootNode = node;
            }
            else if (data > node.data)
            {
                node.right = AddNode(node.right, data);
                node = Shift(node);
            }
            else if (data < node.data)
            {
                node.left = AddNode(node.left, data);
                node = Shift(node);
            }
            return node;
        }

        static int count = 0;
        public void LeftMost(BinarySearchTreeNode node, int val)
        {
            if (node == null || node.data == val)
                return;
            else if (val > node.data)
            {
                count++;
                LeftMost(node.right, val);
            }
            else if (val < node.data)
            {
                count++;
                LeftMost(node.left, val);
            }

            if (node == rootNode)
            {
                while (count > 0)
                {
                    if (node.left != null)
                        node = node.left;
                    else node = node.right;
                    count--;
                }
                Console.WriteLine(node.data);
            }
        }

        

        protected virtual BinarySearchTreeNode Shift(BinarySearchTreeNode node)
        {
            return node;
        }

        protected void ReadInput(int[] input)
        {
            foreach (int item in input)
                this.Add(item);
        }
    }

    class BinarySearchTreeNode
    {
        public int data;
        public BinarySearchTreeNode left;
        public BinarySearchTreeNode right;
        public bool balanced = true;

        public BinarySearchTreeNode(int data)
        {
            this.data = data;
        }
    }
}
